package blue_bridge_cup_learning.data_struct_code;

import java.util.*;
import java.util.Queue;

public class Tree {
    private TreeNode root;

    public class TreeNode {
        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public Tree(int value) {
        this.root = new TreeNode(value);
    }

    public TreeNode add(int value, TreeNode current) {

        if (current == null) {
            return new TreeNode(value);
        }
        if (value < current.value) {
            current.left = add(value, current.left);
        }
        if (value > current.value) {
            current.right = add(value, current.right);
        }
        return current;
    }

    // 前序遍历出来的第一个节点是该数的根节点
    // 递归打印树(中序遍历)
    public void printTree(TreeNode root) {
        if (root != null) {
            printTree(root.left);
            System.out.print(root.value + " ");
            printTree(root.right);
        }
    }

    // 递归打印树(前序遍历)
    public void printTreePre(TreeNode root) {
        if (root != null) {
            System.out.print(root.value + " ");
            printTreePre(root.left);
            printTreePre(root.right);
        }
    }

    // 递归打印树(后序遍历)
    public void printTreePost(TreeNode root) {
        if (root != null) {
            printTreePost(root.left);
            printTreePost(root.right);
            System.out.print(root.value + " ");
        }
    }

    public void getPreOrder(int[] inorder, int[] postorder) {
        List<Integer> preorder = new ArrayList<>();
        getPreOrderHelper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1, preorder);
        System.out.println(preorder);
    }

    private static void getPreOrderHelper(int[] inorder, int[] postorder, int instart, int inend, int poststart,
            int postend, List<Integer> preorder) {
        if (instart > inend) {
            return;
        }
        // 因为后序遍历的最后一个节点是根节点
        // 所以直接按列表的索引取值
        int rootValue = postorder[postend];
        // 将此时的根节点加入到前序遍历的列表中
        preorder.add(rootValue);
        // 找到此时的根节点在中序遍历中的位置
        int rootIndex = instart;
        // instart ->中序遍历的开始位置
        // inend ->中序遍历的结束位置
        for (int i = instart; i <= inend; i++) {
            if (inorder[i] == rootValue) {
                // 找到根节点在中序遍历中的位置
                rootIndex = i;
                break;
            }
        }
        // 左子树的节点个数
        int leftSubtreeSize = rootIndex - instart;
        // 递归处理左子树
        // 以{2, 3, 4, 5, 6, 7, 8}
        // {2, 4, 3, 5, 8, 7, 6};为例
        // 第一次 : 找到根节点6,并找到根节点在中序遍历中的索引值 4,
        // 左子树有2,3,4,5,右子树有7,8
        // 左子树有4个节点,右子树有2个节点
        // 所以此时更新左子树的后续遍历{2,4,3,5}
        // 更新右子树的后续遍历{8,7}
        // 此时列表为{6}
        // 第二次 ：先找左子树的根节点5,并加入列表中
        // 让后以5为根节点再次将{2,4,3,5}分为左右子树，此时右子树为空左子树有三个节点
        // 所以此时更新左子树的后续遍历{2,4,3}
        // 更新右子树的后续遍历{}
        // 此时列表为{6,5}
        // 第三次 ：先找左子树的根节点3,并加入列表中
        // 让后以3为根节点再次将{2,4,3}分为左右子树，此时右子树为空左子树有两个节点
        // 所以此时更新左子树的后续遍历{2,4}
        // 更新右子树的后续遍历{}
        // 此时列表为{6,5,3}
        // 然后一次类推最后列表为{6,5,3,2,4,7,8}
        getPreOrderHelper(inorder, postorder, instart, rootIndex - 1, poststart, poststart + leftSubtreeSize - 1,
                preorder);
        // 递归处理右子树
        getPreOrderHelper(inorder, postorder, rootIndex + 1, inend, poststart + leftSubtreeSize, postend - 1, preorder);
    }

    // 层序遍历
    // 层序遍历 - 打印每一层
    public void printCengOrderByLevel(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            // 获取当前层的节点数
            int levelSize = queue.size();

            // 打印当前层的所有节点
            System.out.print("当前层的节点: ");
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                System.out.print(node.value + " ");

                // 将下一层的节点加入队列
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            // 每层打印完换行
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Tree tree = new Tree(6);
        tree.add(5, tree.root);
        tree.add(3, tree.root);
        tree.add(7, tree.root);
        tree.add(2, tree.root);
        tree.add(4, tree.root);
        tree.add(6, tree.root);
        tree.add(8, tree.root);
        System.out.println("中序遍历:");
        tree.printTree(tree.root);
        System.out.println();

        System.out.println("前序遍历:");
        tree.printTreePre(tree.root);
        System.out.println();

        System.out.println("后序遍历:");
        tree.printTreePost(tree.root);
        System.out.println();
        int[] inorder = { 2, 3, 4, 5, 6, 7, 8 }; // 中序遍历
        int[] postorder = { 2, 4, 3, 5, 8, 7, 6 }; // 后序遍历
        tree.getPreOrder(inorder, postorder); // 输出：[6, 5, 3, 2, 4, 7, 8]
        System.out.println("---------------------------");
        tree.printCengOrderByLevel(tree.root);
    }
}
